package bin_tree.leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * @author shkstart
 * 后序+中序
 * @create 2022-10-24-22:44
 */
public class Num106 {
//    存储中序遍历的对应的值和索引
    Map<Integer,Integer> map = new HashMap<>();
    public TreeNode buildTree(int[] inorder, int[] postorder) {
//        将后序遍历结果反转
        int[] preOrder = reverse(inorder,postorder);
return buildTreeInternal(preOrder,inorder,0,inorder.length);
    }
    int index = 0;
    public TreeNode buildTreeInternal(int[] preOrder, int[] inOrder, int left, int right) {
//        边界
        if (left >= right) {
//            空区间，说明中序结果为空，空树
            return null;
        }
        if (index >= preOrder.length) {
//            所有节点已经处理完毕
            return null;
        }
//        此时前序结果还有没处理的元素，从index位置获取一个元素构建根节点
        TreeNode root = new TreeNode(preOrder[index]);
//        继续处理下一个节点
        index++;
//        处理左树
//        拿着根节点root.val去从中序遍历中找到该值对应的索引pos
        int pos = map.get(root.val);
//        左树
        root.right = buildTreeInternal(preOrder,inOrder,pos+1,right);
        root.left = buildTreeInternal(preOrder,inOrder,left,pos);
        return root;
    }
    private  int[] reverse(int[] inorder,int[] postorder){
        int[] ret = new int[postorder.length];
        for (int i = 0; i < ret.length; i++) {
            ret[i]=postorder[ret.length-1-i];
            
        }
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);

        }
        return ret;
    }

}
